package com.ljy.kotlindemo.leetcode

import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

/**
 * @Author:         LiuJinYang
 * @CreateDate:     2020/12/2
 * 大厂 客户端 算法题
 */
class ListNode {
    var `val` = 0
    var next: ListNode? = null

    internal constructor(data: Int) {
        this.`val` = data
    }

    internal constructor(data: Int, next: ListNode?) {
        this.`val` = data
        this.next = next
    }

    fun print() {
        print("$`val`-->")
        if (next != null) {
            next?.print()
        } else {
            println("null")
        }

    }
}


/**
206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */
fun _0206_reverseList() {
    println("--------_0206_reverseList-------")
    reverseList(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))))?.print()
}

fun reverseList(head: ListNode?): ListNode? {
    //递归终止条件是当前为空，或者下一个节点为空
    if (head?.next == null) {
        return head
    }
    //这里的cur就是最后一个节点
    val cur = reverseList(head.next)
    ////如果链表是 1->2->3->4->5，那么此时的cur就是5
    //而head是4，head的下一个是5，下下一个是空
    //所以head.next.next 就是5->4
    head.next?.next = head
    //防止链表循环，需要将head.next设置为空
    head.next = null
    //每层递归函数都返回cur，也就是最后一个节点
    return cur
}

/**
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 */
fun _0053_maxSubArray() {
    println("--------_0053_maxSubArray-------")
    println(maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)))
}

/**
贪心算法
类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
 */
fun maxSubArray(nums: IntArray): Int {
    var result = Int.MIN_VALUE
    var sum = 0
    for (i in nums.indices) {
        sum += nums[i]
        result = Math.max(result, sum)
        //如果sum < 0，重新开始找子序串
        if (sum < 0)
            sum = 0
    }
    return result
}

/**
160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，
链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，
链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，
所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 */
fun _0160_getIntersectionNode() {
    println("--------_0160_getIntersectionNode-------")
    getIntersectionNode(
        ListNode(4, ListNode(1, ListNode(8, ListNode(4, ListNode(5))))),
        ListNode(5, ListNode(0, ListNode(1, ListNode(8, ListNode(4, ListNode(5))))))
    )?.print()
    getIntersectionNode(
        ListNode(0, ListNode(9, ListNode(1, ListNode(2, ListNode(4))))),
        ListNode(3, ListNode(2, ListNode(4)))
    )?.print()
    getIntersectionNode(
        ListNode(2, ListNode(6, ListNode(4))),
        ListNode(1, ListNode(5))
    )?.print() ?: println("null")
}

fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    if (headA == null || headB == null) return null
    var pA = headA
    var pB = headB
    while (pA?.`val` != pB?.`val`) {
        pA = if (pA == null) headB else pA.next
        pB = if (pB == null) headA else pB.next
    }
    return pA
}

/**
 * 25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
fun _0025_reverseKGroup() {
    println("--------_0025_reverseKGroup-------")
    reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2)?.print()
    reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 3)?.print()
    reverseKGroup(
        ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
        2
    )?.print()
    reverseKGroup(
        ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
        3
    )?.print()
    reverseKGroup(
        ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
        4
    )?.print()
}

/**
 * 首先遍历整个链表，统计出链表的长度，然后如果长度大于等于k，交换节点，当 k=2 时，每段只需要交换一次，
 * 当 k=3 时，每段需要交换2此，所以i从1开始循环，注意交换一段后更新 pre 指针，然后 num 自减k，
 * 直到 num<k 时循环结束
 */
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    var dummy = ListNode(-1)
    var pre: ListNode? = dummy
    var cur: ListNode? = pre
    dummy.next = head
    var num = 0
    while (cur?.next != null) {
        cur = cur.next
        ++num
    }
    while (num >= k) {
        cur = pre?.next
        for (i in 1 until k) {
            var temp = cur?.next
            cur?.next = temp?.next
            temp?.next = pre?.next
            pre?.next = temp
        }
        pre = cur
        num -= k
    }
    return dummy.next
}

/**
215. 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 */
fun _0215_findKthLargest() {
    println("--------_0215_findKthLargest-------")
    println(findKthLargest(intArrayOf(3, 2, 1, 5, 6, 4), 2))
    println(findKthLargest(intArrayOf(3, 2, 3, 1, 2, 4, 5, 5, 6), 4))
}

/**
 * 使用优先队列
 */
fun findKthLargest(nums: IntArray, k: Int): Int {
    val len = nums.size
    //// 使用一个含有 len 个元素的最小堆
    val minHeap = PriorityQueue<Int>(len) { o1, o2 -> o1 - o2 }
    for (i in nums.indices) {
        minHeap.add(nums[i])
    }
    for (j in 0 until len - k) {
        minHeap.poll()
    }
    return minHeap.peek()!!
}
//fun findKthLargest(nums: IntArray, k: Int): Int {
//    val len=nums.size
//    Arrays.sort(nums)
//    return nums[len-k]
//}
/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
 */
fun _0021_mergeTwoLists() {
    println("--------_0021_mergeTwoLists-------")
    mergeTwoLists(
        ListNode1(1, ListNode1(2, ListNode1(4))),
        ListNode1(1, ListNode1(3, ListNode1(4)))
    )?.print()
}

/**
 * 递归写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，
 * 那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；
 * 否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2
 */
fun mergeTwoLists(l1: ListNode1?, l2: ListNode1?): ListNode1? {
    if (l1 == null) return l2
    if (l2 == null) return l1
    return if (l1.data < l2.data) {
        l1.next = mergeTwoLists(l1.next, l2);l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next);l2
    }
}


/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */
fun _0003_lengthOfLongestSubstring() {
    println("--------_003_lengthOfLongestSubstring-------")
    lengthOfLongestSubstring("abcabcbb")
    lengthOfLongestSubstring("bbbbb")
    lengthOfLongestSubstring("pwwkew")
    lengthOfLongestSubstring("pwwkewabcdefghijkabcabc")
}

/**
 * 使用了 HashSet，把出现过的字符都放入 HashSet 中，遇到 HashSet 中没有的字符就加入 HashSet 中
 * 并更新结果 res，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止：
 */
fun lengthOfLongestSubstring(s: String) {
    var maxLen = 0
    var left = 0
    var right = 0
    val temp = HashSet<Char>()
    while (right < s.length) {
        if (!temp.contains(s[right])) {
            temp.add(s[right++])
            maxLen = Math.max(maxLen, temp.size)
        } else {
            temp.remove(s[left++])
        }
    }
    println("len：$maxLen")
}

/**
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
 */
fun _0236_lowestCommonAncestor() {
    println("--------_0236_lowestCommonAncestor-------")
    val t3 = TreeNode(3)
    val t5 = TreeNode(5)
    val t1 = TreeNode(1)
    val t6 = TreeNode(6)
    val t2 = TreeNode(2)
    val t0 = TreeNode(0)
    val t8 = TreeNode(8)
    val t7 = TreeNode(7)
    val t4 = TreeNode(4)
    t3.left = t5
    t3.right = t1
    t5.left = t6
    t5.right = t2
    t2.left = t7
    t2.right = t4
    t1.left = t0
    t1.right = t8

    println(lowestCommonAncestor(t3, t5, t1)?.`val`)
    println(lowestCommonAncestor(t3, t5, t4)?.`val`)
}

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || root == p || root == q) return root
    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)
    if (left == null) return right
    if (right == null) return left
    return root
}


/**
146. LRU 缓存机制
运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。
当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put
 */
fun _0146_LRUCache() {
    println("--------_0146_LRUCache-------")
    val lRUCache = LRUCache(2);
    lRUCache.put(1, 1) // 缓存是 {1=1}
    lRUCache.put(2, 2) // 缓存是 {1=1, 2=2}
    println("LruCache.get: ${lRUCache.get(1)}")   // 返回 1
    lRUCache.put(3, 3) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    println("LruCache.get: ${lRUCache.get(2)}")   // 返回 -1 (未找到)
    lRUCache.put(4, 4) // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    println("LruCache.get: ${lRUCache.get(1)}")   // 返回 -1 (未找到)
    println("LruCache.get: ${lRUCache.get(3)}")    // 返回 3
    println("LruCache.get: ${lRUCache.get(4)}")   // 返回 4
}

/**
 * 双链表的节点类
 */
class LRUCache(capacity: Int) {
    internal inner class DLinkedNode {
        var key = 0
        var value = 0
        var prev: DLinkedNode? = null
        var next: DLinkedNode? = null

        constructor()
        constructor(_key: Int, _value: Int) {
            key = _key
            value = _value
        }
    }

    private val cache: MutableMap<Int, DLinkedNode> = HashMap()
    private var size: Int = 0
    private val capacity: Int = capacity
    private val head: DLinkedNode
    private val tail: DLinkedNode
    operator fun get(key: Int): Int {
        val node = cache[key] ?: return -1
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        val node = cache[key]
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            val newNode = DLinkedNode(key, value)
            // 添加进哈希表
            cache[key] = newNode
            // 添加至双向链表的头部
            addToHead(newNode)
            ++size
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                val tail = removeTail()
                // 删除哈希表中对应的项
                cache.remove(tail!!.key)
                --size
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value
            moveToHead(node)
        }
    }

    private fun addToHead(node: DLinkedNode) {
        node.prev = head
        node.next = head.next
        head.next!!.prev = node
        head.next = node
    }

    private fun removeNode(node: DLinkedNode?) {
        node!!.prev!!.next = node.next
        node.next!!.prev = node.prev
    }

    private fun moveToHead(node: DLinkedNode) {
        removeNode(node)
        addToHead(node)
    }

    private fun removeTail(): DLinkedNode? {
        val res = tail.prev
        removeNode(res)
        return res
    }

    init {
        // 使用伪头部和伪尾部节点
        head = DLinkedNode()
        tail = DLinkedNode()
        head.next = tail
        tail.prev = head
    }
}

/**
 * 1. 两数之和
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
 */
fun _0001_twoSum() {
    println("--------_0001_twoSum-------")
    val nums = intArrayOf(2, 7, 11, 15)
    for (i in twoSum(nums, 9)) {
        println(i)
    }
}

/**
 * 这道 Two Sum 的题目作为 LeetCode 的开篇之题，乃是经典中的经典，正所谓‘ 平生不识 TwoSum，刷尽 LeetCode 也枉然
 */
fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for (i in nums.indices) {
        if (map.containsKey(target - nums[i])) {
            return intArrayOf(map[target - nums[i]]!!, i)
        }
        map[nums[i]] = i
    }
    return intArrayOf()
}

/**
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
 */
fun JZOffer_09() {
    println("--------JZOffer_09-------")
    val cQueue = CQueue()
    cQueue.appendTail(3)
    println(cQueue.deleteHead())
    println(cQueue.deleteHead())
    val cQueue2 = CQueue()
    println(cQueue2.deleteHead())
    cQueue2.appendTail(5)
    cQueue2.appendTail(2)
    println(cQueue2.deleteHead())
    println(cQueue2.deleteHead())

}

class CQueue() {
    private val stack1 = Stack<Int>()
    private val stack2 = Stack<Int>()

    fun appendTail(value: Int) {
        stack1.push(value)
    }

    fun deleteHead(): Int {
        if (!stack2.isEmpty()) {
            return stack2.pop()
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop())
            }
        }
        return if (stack2.isEmpty()) -1 else stack2.pop()
    }
}

/**
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？

前序遍历： 0144.二叉树的前序遍历
后序遍历： 0145.二叉树的后序遍历
中序遍历： 0094.二叉树的中序遍历
 */
fun _0144_preorderTraversal() {
    println("--------_0144_preorderTraversal-------")
    val t1 = TreeNode(1)
    val t2 = TreeNode(2)
    val t4 = TreeNode(4)
    val t5 = TreeNode(5)
    val t6 = TreeNode(6)
    val t7 = TreeNode(7)
    val t8 = TreeNode(8)
    t5.left = t4
    t5.right = t6
    t4.left = t1
    t4.right = t2
    t6.left = t7
    t6.right = t8
    println("递归法：")
    print("前序遍历")
    preOrder(t5)
    println()
    print("中序遍历")
    inOrder(t5)
    println()
    print("后序遍历")
    postOrder(t5)
    println()
    println("迭代法：")
    print("前序遍历")
    preOrderIter(t5)
    println()
    print("中序遍历")
    inOrderIter(t5)
    println()
    print("后序遍历")
    postOrderIter(t5)
    println()
}

/**
- 满二叉树：只有度为0的结点和度为2的结点，并且度为0的结点在同一层上
- 完全二叉树: 除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置
- 二叉搜索树: 左子树上所有结点的值均小于它的根结点的值,右子树上所有结点的值均大于它的根结点的值,左、右子树也分别为二叉排序树
- 平衡二叉搜索树: 一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
- 二叉树的存储方式:
1. 链式存储-指针,通过指针把分布在散落在各个地址的节点串联一起
2. 顺序存储-数组(一层一层依次存储到数组，如果父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2),内存是连续分布的
- 二叉树的遍历方式:
1. 深度优先遍历：先往深走，遇到叶子节点再往回走
- 这里前中后，其实指的就是中间节点的遍历顺序（递归法，迭代法）
- 5461278
1. 前序遍历:中左右 5412678
2. 中序遍历:左中右 1425768
3. 后序遍历:左右中 1247865
2. 广度优先遍历：一层一层的去遍历
- 层次遍历（迭代法）
 */
class TreeNode(var `val`: Int = 0) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

/**
 * 递归法-前序遍历
 */
fun preOrder(root: TreeNode?) {
    if (root == null)
        return
    print(" ${root.`val`}")
    preOrder(root.left)
    preOrder(root.right)
}

/**
 * 递归法-中序遍历
 */
fun inOrder(root: TreeNode?) {
    if (root == null)
        return
    inOrder(root.left)
    print(" ${root.`val`}")
    inOrder(root.right)
}

/**
 * 递归法-后序遍历
 */
fun postOrder(root: TreeNode?) {
    if (root == null)
        return
    postOrder(root.left)
    postOrder(root.right)
    print(" ${root.`val`}")
}

/**
 * 迭代法-前序遍历
 * 本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈
 */
fun preOrderIter(root: TreeNode?) {
    if (root == null)
        return
    val stack = Stack<TreeNode>()
    stack.push(root)
    while (stack.isNotEmpty()) {
        val node = stack.pop()
        print(" ${node.`val`}")
        if (node.right != null) {
            stack.push(node.right)
        }
        if (node.left != null) {
            stack.push(node.left)
        }
    }
}

/**
 * 迭代法-中序遍历
 */
fun inOrderIter(root: TreeNode?) {
    if (root == null)
        return
    var cur = root
    val stack = Stack<TreeNode>()
    while (stack.isNotEmpty() || cur != null) {
        while (cur != null) {
            stack.push(cur)
            cur = cur.left
        }
        val node = stack.pop()
        print(" ${node.`val`}")
        if (node.right != null) {
            cur = node.right
        }
    }
}

/**
 * 迭代法-后序遍历
 */
fun postOrderIter(root: TreeNode?) {
    if (root == null)
        return
    val stack1 = Stack<TreeNode>()
    val stack2 = Stack<TreeNode>()
    stack1.push(root)
    while (stack1.isNotEmpty()) {
        val node = stack1.pop()
        stack2.push(node)
        if (node.left != null) {
            stack1.push(node.left)
        }
        if (node.right != null) {
            stack1.push(node.right)
        }
    }
    while (stack2.isNotEmpty()) {
        print(" ${stack2.pop().`val`}")
    }
}

/**
199. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1            <---
/   \
2     3         <---
\     \
5     4       <---
 */
fun _0199_rightSideView() {
    println("--------_0199_rightSideView-------")
    val t1 = TreeNode(1)
    val t2 = TreeNode(2)
    val t3 = TreeNode(3)
    val t4 = TreeNode(4)
    val t5 = TreeNode(5)
    val t6 = TreeNode(6)
    t1.left = t2
    t1.right = t3
    t2.right = t5
    t3.right = t4
    println(rightSideView(t1))
    t5.left = t6
    println(rightSideView(t1))
}

fun rightSideView(root: TreeNode?): List<Int> {
    val res = ArrayList<Int>()
    fun dfs(root: TreeNode?, depth: Int) {
        var depth = depth
        if (root == null)
            return
        if (depth == res.size)
            res.add(root.`val`)
        depth++
        dfs(root.right, depth)//右视图就先递归右，左视图就先递归左
        dfs(root.left, depth)
    }
    dfs(root, 0)
    return res
}

/**
 * 121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 */
fun _0121_maxProfit() {
    println("--------_0121_maxProfit-------")
    println(maxProfit(intArrayOf(7, 1, 5, 3, 6, 4)))
    println(maxProfit(intArrayOf(7, 6, 4, 3, 1)))
}

fun maxProfit(prices: IntArray): Int {
    var res = 0
    var buy = Int.MAX_VALUE
    for (price in prices) {
        buy = Math.min(buy, price)
        res = Math.max(res, price - buy)
    }
    return res
}

/**
 * 122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
 */
fun _0122_maxProfit2() {
    println("--------_122_maxProfit2-------")
    println(maxProfit2(intArrayOf(7, 1, 5, 3, 6, 4)))
    println(maxProfit2(intArrayOf(1, 2, 3, 4, 5)))
    println(maxProfit2(intArrayOf(7, 6, 4, 3, 1)))
}

fun maxProfit2(prices: IntArray): Int {
    var res = 0
    for (i in 0 until prices.size - 1) {
        if (prices[i] < prices[i + 1]) {
            res += prices[i + 1] - prices[i]
        }
    }
    return res
}

/**
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
 */
fun _0123_maxProfit3() {
    println("--------_123_maxProfit3-------")
    println(maxProfit3(intArrayOf(3, 3, 5, 0, 0, 3, 1, 4)))
    println(maxProfit3(intArrayOf(1, 2, 3, 4, 5)))
    println(maxProfit3(intArrayOf(7, 6, 4, 3, 1)))
}

fun maxProfit3(prices: IntArray): Int {
    val len = prices.size
    if (len < 2)
        return 0
    // 第 1 维的 0 没有意义，1 表示交易进行第一笔，2 表示交易进行第二笔
    // 为了使得第 1 维的数值 1 和 2 有意义，这里将第 1 维的长度设置为 3
    //第2维，1表示买入，0表示卖出
    val dp = Array(3) { IntArray(2) }
    //规定了必须持股，因此是 -prices[0]
    dp[1][1] = -prices[0]
    //还没发生的交易，持股的时候应该初始化为负无穷
    dp[2][1] = Int.MIN_VALUE
    for (i in 1 until len) {
        dp[1][1] = Math.max(dp[1][1], -prices[i])
        dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])
        dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])
        dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])
    }
    return Math.max(dp[1][0], dp[2][0])
}

/**
188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 109
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
 */
fun _0188_maxProfit4() {
    println("--------_0188_maxProfit4-------")
    println(maxProfit4(2, intArrayOf(3, 3, 5, 0, 0, 3, 1, 4)))
    println(maxProfit4(2, intArrayOf(1, 2, 3, 4, 5)))
    println(maxProfit4(2, intArrayOf(7, 6, 4, 3, 1)))
}

fun maxProfit4(k: Int, prices: IntArray): Int {
    val len = prices.size
    if (k == 0 || len < 2)
        return 0
    if (k > len / 2)
        return greedy(prices)
    val dp = Array(k + 1) { IntArray(2) }
    for (i in 0..k)
        dp[i][1] = Int.MIN_VALUE

    for (p in prices)
        for (j in 1..k) {
            dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - p)
            dp[j][0] = Math.max(dp[j][0], dp[j][1] + p)
        }
    return dp[k][0]
}

fun greedy(prices: IntArray): Int {
    var res = 0
    for (i in 1 until prices.size) {
        if (prices[i] > prices[i - 1]) {
            res += prices[i] - prices[i - 1]
        }
    }
    return res
}

/**
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 */
fun _0309_maxProfit5() {
    println("--------_0309_maxProfit5-------")
    println(maxProfit5(intArrayOf(1, 2, 3, 0, 2)))
}

fun maxProfit5(prices: IntArray): Int {
    val len = prices.size
    if (len < 2) {
        return 0
    }
    val dp = IntArray(3)
    dp[0] = 0
    dp[1] = -prices[0]
    dp[2] = 0
    var pre0 = dp[0]
    var pre2 = dp[2]
    for (i in 1 until len) {
        dp[0] = Math.max(dp[0], pre2)
        dp[1] = Math.max(dp[1], pre0 - prices[i])
        dp[2] = dp[1] + prices[i]
        pre0 = dp[0]
        pre2 = dp[2]
    }
    return Math.max(dp[0], dp[2])
}

/**
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
 */
fun _0714_maxProfit6() {
    println("--------_0714_maxProfit6-------")
    println(maxProfit6(intArrayOf(1, 3, 2, 8, 4, 9), 2))
}

fun maxProfit6(prices: IntArray, fee: Int): Int {
    val len = prices.size
    if (len < 2) {
        return 0
    }
    // j = 0 表示不持股，j = 1 表示持股
    // 并且规定在买入股票的时候，扣除手续费
    val dp = IntArray(2)
    dp[0] = 0
    dp[1] = -prices[0] - fee
    for (i in 1 until len) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], dp[0] - prices[i] - fee)
    }
    return dp[0]
}

/**
 * 48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
 */
fun _0048_rotate() {
    println("--------_0048_rotate-------")
    rotate(arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6), intArrayOf(7, 8, 9)))
    rotate(
        arrayOf(
            intArrayOf(5, 1, 9, 11),
            intArrayOf(2, 4, 8, 10),
            intArrayOf(13, 3, 6, 7),
            intArrayOf(15, 14, 12, 16)
        )
    )
}

/**
按顺时针的顺序去覆盖前面的数字，从四个顶角开始，然后往中间去遍历，每次覆盖的坐标都是同理
 */
fun rotate(matrix: Array<IntArray>) {
    val n = matrix.size
    for (i in 0 until n / 2) {
        for (j in i until n - 1 - i) {
            val temp = matrix[i][j]
            matrix[i][j] = matrix[n - 1 - j][i]
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
            matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
            matrix[j][n - 1 - i] = temp
        }
    }
    for (item in matrix) {
        println(item.contentToString())
    }
    println()
}

/**
 * 76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
 */
fun _0076_minWindow() {
    println("--------_0076_minWindow-------")
    println(minWindow("ADOBECODEBANC", "ABC"))
}

fun minWindow(s: String?, t: String?): String {
    if (s == null || s.isEmpty() || t == null || t.isEmpty())
        return ""
    val need = IntArray(128)
    //记录需要的字符个数
    for (c in t) {
        need[c.toInt()]++
    }
    var left = 0
    var right = 0
    var size = Int.MAX_VALUE
    var count = t.length
    var start = 0
    while (right < s.length) {
        val c = s[right]
        if (need[c.toInt()] > 0)
            count--
        need[c.toInt()]--
        if (count == 0) {
            while (left < right && need[s[left].toInt()] < 0) {
                need[s[left].toInt()]++
            }
            if (right - left + 1 < size) {
                size = right - left + 1
                left++
            }
            if (right - left + 1 < size) {
                size = right - left + 1
                start = left
            }
            need[s[left].toInt()]++
            left++
            count++
        }
        right++
    }
    return if (size == Int.MAX_VALUE) "" else s.substring(start, start + size)
}

/**
700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
4
/ \
2   7
/ \
1   3
和值: 2
你应该返回如下子树:
2
/ \
1   3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
 */
fun _0700_searchBST() {
    println("--------_0700_searchBST-------")
    val t4 = TreeNode(4)
    val t2 = TreeNode(2)
    val t7 = TreeNode(7)
    t4.left = t2
    t4.right = t7
    val t1 = TreeNode(1)
    val t3 = TreeNode(3)
    t2.left = t1
    t2.right = t3
    println(searchBST(t4, 2))
    println(searchBST(t4, 5))
}

/**
 * 二叉搜索树是一棵二叉树，每个节点都有以下特性：
 * 大于左子树上任意一个节点的值，
 * 小于右子树上任意一个节点的值。
 */
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
    //方法1：递归
    if (root == null || `val` == root.`val`) return root
    return if (`val` < root.`val`) searchBST(root.left, `val`) else searchBST(root.right, `val`)
    //方法2：迭代
    var root = root
    while (root != null && `val` != root.`val`)
        root = if (`val` < root.`val`) root.left else root.right
    return root
}

/**
319. 灯泡开关
初始时有 n 个灯泡关闭。
第 1 轮，你打开所有的灯泡。
第 2 轮，每两个灯泡你关闭一次。
第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。
第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。

示例 1：
输入：n = 3
输出：1
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着。

示例 2：
输入：n = 0
输出：0

示例 3：
输入：n = 1
输出：1

提示：
0 <= n <= 109
 */
fun _0319_bulbSwitch() {
    println("--------_0319_bulbSwitch-------")
    println(bulbSwitch(3))
    println(bulbSwitch(2))
    println(bulbSwitch(1))
    println(bulbSwitch(0))
}

fun bulbSwitch(n: Int): Int {
    if (n == 1)
        return 1
    var result = 1
    while (true) {
        if (result * result > n)
            break
        result++
    }
    return result - 1
}

/**
672. 灯泡开关 Ⅱ
现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。
在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：
将所有灯泡的状态反转（即开变为关，关变为开）
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)

示例 1:
输入: n = 1, m = 1.
输出: 2
说明: 状态为: [开], [关]

示例 2:
输入: n = 2, m = 1.
输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]

示例 3:
输入: n = 3, m = 1.
输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].

注意： n 和 m 都属于 [0, 1000].
 */
fun _0672_flipLights() {
    println("--------_0672_flipLights-------")
    println(flipLights(1, 1))
    println(flipLights(2, 1))
    println(flipLights(3, 1))
}

/**
因为前 6 个灯唯一地决定了其余的灯。
这是因为修改第 xx 灯光的每个操作都会修改 第 (x+6)(x+6) 灯光，
因此 xx 灯光始终等于 (x+6)(x+6) 灯光。
实际上，前 3 个灯唯一地确定了序列的其余部分
 */
fun flipLights(n: Int, m: Int): Int {
    val n = Math.min(n, 3)
    if (m == 0) return 1
    if (m == 1) return if (n == 1) 2 else if (n == 2) 3 else 4
    if (m == 2) return if (n == 1) 2 else if (n == 2) 4 else 7
    return if (n == 1) 2 else if (n == 2) 4 else 8
}

/**
1375. 灯泡开关 III
房间中有 n 枚灯泡，编号从 1 到 n，自左向右排成一排。最初，所有的灯都是关着的。
在 k  时刻（ k 的取值范围是 0 到 n - 1），我们打开 light[k] 这个灯。
灯的颜色要想 变成蓝色 就必须同时满足下面两个条件：
灯处于打开状态。
排在它之前（左侧）的所有灯也都处于打开状态。
请返回能够让 所有开着的 灯都 变成蓝色 的时刻 数目 。

示例 1：
输入：light = [2,1,3,5,4]
输出：3
解释：所有开着的灯都变蓝的时刻分别是 1，2 和 4 。

示例 2：
输入：light = [3,2,4,1,5]
输出：2
解释：所有开着的灯都变蓝的时刻分别是 3 和 4（index-0）。

示例 3：
输入：light = [4,1,2,3]
输出：1
解释：所有开着的灯都变蓝的时刻是 3（index-0）。
第 4 个灯在时刻 3 变蓝。

示例 4：
输入：light = [2,1,4,3,6,5]
输出：3

示例 5：
输入：light = [1,2,3,4,5,6]
输出：6

提示：
n == light.length
1 <= n <= 5 * 10^4
light 是 [1, 2, ..., n] 的一个排列。
 */
fun _1375_numTimesAllBlue() {
    println("--------_1375_numTimesAllBlue-------")
    println(numTimesAllBlue(intArrayOf(2, 1, 3, 5, 4)))
    println(numTimesAllBlue(intArrayOf(3, 2, 4, 1, 5)))
    println(numTimesAllBlue(intArrayOf(4, 1, 2, 3)))
    println(numTimesAllBlue(intArrayOf(2, 1, 4, 3, 6, 5)))
    println(numTimesAllBlue(intArrayOf(1, 2, 3, 4, 5, 6)))
}

fun numTimesAllBlue(light: IntArray): Int {
    var result = 0
    var curMax = 0
    for (i in light.indices) {
        curMax = Math.max(curMax, light[i])
        if (curMax == i + 1)
            result++
    }
    return result
}

/**
1529. 灯泡开关 IV
房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着的。
有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：
选择当前配置下的任意一个灯泡（下标为 i ）
翻转下标从 i 到 n-1 的每个灯泡
翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。
返回达成 target 描述的状态所需的 最少 翻转次数。

示例 1：
输入：target = "10111"
输出：3
解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态

示例 2：
输入：target = "101"
输出：3
解释："000" -> "111" -> "100" -> "101".

示例 3：
输入：target = "00000"
输出：0

示例 4：
输入：target = "001011101"
输出：5

提示：
1 <= target.length <= 10^5
target[i] == '0' 或者 target[i] == '1'
 */
fun _1529_minFlips() {
    println("--------_1529_minFlips-------")
    println(minFlips("10111"))
    println(minFlips("101"))
    println(minFlips("00000"))
    println(minFlips("001011101"))
}

fun minFlips(target: String): Int {
    var target = "0$target"
    var res = 0
    for (i in 1 until target.length)
        if (target[i] != target[i - 1]) ++res
    return res
}

/**
683. K 个关闭的灯泡
N 个灯泡排成一行，编号从 1 到 N 。
最初，所有灯泡都关闭。每天只打开一个灯泡，直到 N 天后所有灯泡都打开。
给你一个长度为 N 的灯泡数组 blubs ，其中 bulls[i] = x 意味着在第 (i+1) 天，
我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。
给你一个整数 K ，请你输出在第几天恰好有两个打开的灯泡，
使得它们中间 正好 有 K 个灯泡且这些灯泡 全部是关闭的 。
如果不存在这种情况，返回 -1 。如果有多天都出现这种情况，请返回 最小的天数 。
 */
fun _0683_kEmptySlots() {
    println("--------_0683_kEmptySlots-------")
    println(kEmptySlots(intArrayOf(1,3,2),1))// 2
    println(kEmptySlots(intArrayOf(1,2,3),1))//-1
}
fun kEmptySlots(flowers: IntArray, k: Int): Int {
    val n = flowers.size
    if (n == 1 && k == 0) {
        return 1
    }
    val sort: TreeSet<Int> = TreeSet()
    for (i in 0 until n) {
        sort.add(flowers[i])
        val min = sort.lower(flowers[i])
        val max = sort.higher(flowers[i])
        if (min != null && flowers[i] - min == k + 1) {
            return i + 1
        }
        if (max != null && max - flowers[i] == k + 1) {
            return i + 1
        }
    }
    return -1
}


fun main() {
    _0700_searchBST()

    _0319_bulbSwitch()
    _0672_flipLights()
    _1375_numTimesAllBlue()
    _1529_minFlips()
    _0683_kEmptySlots()
//    _0048_rotate()
//    _0206_reverseList()
//    _0215_findKthLargest()
//    _0076_minWindow()
//
//
//    _0053_maxSubArray()
//    _0160_getIntersectionNode()
//    _0025_reverseKGroup()
//
//    _0021_mergeTwoLists()
//    _0003_lengthOfLongestSubstring()
//    _0236_lowestCommonAncestor()
//    _0146_LRUCache()
//    _0001_twoSum()
//
//    JZOffer_09()
//    _0144_preorderTraversal()
//    _0199_rightSideView()
//
//    _0121_maxProfit()
//    _0122_maxProfit2()
//    _0123_maxProfit3()
//    _0188_maxProfit4()
//    _0309_maxProfit5()
//    _0714_maxProfit6()
}